/*
 * OptimalMismatch.cpp
 *
 *  Created on: 02-09-2013
 *      Author: Krzychu
 */

#include "OptimalMismatch.h"

#include "Config.h"
#include "OptimalMismatchQuickSort.h"

#include <stdio.h>

#define MAX(a, b) (a > b) ? a : b
#define ASIZE 255

OptimalMismatch::OptimalMismatch()
{

}

OptimalMismatch::~OptimalMismatch()
{

}

std::string OptimalMismatch::getName()
{
	return "Optimal Mismatch";
}

int freq[ASIZE];

/* Construct an ordered pattern from a string. */
void OptimalMismatch::orderPattern(std::string pattern, patStruct *pat)
{
	int patternSize = pattern.size();

	int i;

	for (i = 0; i <= patternSize; i++)
	{
		pat[i].loc = i;
		pat[i].c = pattern[i];
	}

	OptimalMismatchQuickSort::sort(pat, patternSize, freq);
}

/* Find the next leftward matching shift for
 the first ploc pattern elements after a
 current shift or lshift. */
int OptimalMismatch::matchShift(std::string pattern, int ploc, int lshift, patStruct *pat)
{
	int patternSize = pattern.size();

	int i, j;

	for (; lshift < patternSize; ++lshift)
	{
		i = ploc;
		while (--i >= 0)
		{
			if ((j = (pat[i].loc - lshift)) < 0)
			{
				continue;
			}
			if (pat[i].c != pattern[j])
			{
				break;
			}
		}
		if (i < 0)
		{
			break;
		}
	}
	return (lshift);
}

/* Constructs the good-suffix shift table
 from an ordered string. */
int* OptimalMismatch::preAdaptedGs(std::string pattern, patStruct *pat)
{
	int patternSize = pattern.size();

	int* result = new int[patternSize];

	int lshift, i, ploc;

	result[0] = lshift = 1;
	for (ploc = 1; ploc <= patternSize; ++ploc)
	{
		lshift = matchShift(pattern, ploc, lshift, pat);
		result[ploc] = lshift;
	}
	for (ploc = 0; ploc <= patternSize; ++ploc)
	{
		lshift = result[ploc];
		while (lshift < patternSize)
		{
			i = pat[ploc].loc - lshift;
			if (i < 0 || pat[ploc].c != pattern[i])
			{
				break;
			}
			++lshift;
			lshift = matchShift(pattern, ploc, lshift, pat);
		}
		result[ploc] = lshift;
	}

	return result;
}

searchResult OptimalMismatch::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	int i, j;
	patStruct* pat = new patStruct[patternSize + 1];


	/* Preprocessing */
	orderPattern(pattern, pat);
	int* qsBc = preQsBc(pattern);
//	int* adaptedGs = preAdaptedGs(pattern, pat);

	/* Searching */
	j = 0;
	while (j <= textSize - patternSize)
	{
		result.iterationsTaken++;

		i = 0;
		while (i < patternSize && pattern[i] == text[i + j]/*pat[i].c == text[j + pat[i].loc]*/)
		{
			++i;
		}
		if (i >= patternSize)
		{
			result.positionsFound.push_back(j);
			if (Config::getInstance()->getFindOneOccurence())
			{
				return result;
			}
		}
		j += /*MAX(adaptedGs[i],*/qsBc[text[j + patternSize]]/*)*/;
	}

	return result;
}
